Prior art systems which operate in three-level logic
have one of the voltages at a negative level, i.e., voltage levels of -1, 0, +1, which are respectively referred to as data quantities of 0, 1, 2. No prior art systems are known to operate with all voltages at single polarity voltage levels to generate data logic of 0, 1, 2 nor are there any known three-level systems which include error detection or correction.
The use of trinary three-level logic offers a variety of advantages over the familiar binary two-level logic with two of these advantages being a reduction in components and increased data capacity.
However, before trinary data can be depended upon for processing information, there must be an error detection and correction function performed on the data during movement or storage of the data. The use of trinary data is sparse in the prior art. There are no known techniques for trinary data error handling.
Trinary data (described herein as the three logic levels, 0, 1, 2) has been used to transmit data between binary logic units (see U.S. Pat. No. 4,631,428 assigned to International Business Machines Corporation). However, this type of trinary data has not been used to perform logic functions which require error checking. As trinary data and logic become more widely used in data processing as a technique to increase capacity, so will the need to perform error checking and correction.
Some of the broad error detection and correction functions used in binary such as generating parity bits from data; using parity bits to generate syndrome elements; using syndrome elements to detect errors and to generate signals for correction of errors are useful in a general way for trinary. However, the use of the known binary techniques for trinary error detection and correction is not possible without making considerable basic and unique changes to these functions which are not apparent to one attempting to use trinary data.
The binary approach to error detection and correction and the problems associated with applying these techniques to trinary error detection and correction can be described by examining some of the basic prior art:
U.S. Pat. No. 4,523,314 discloses an error indicating system for use with a binary error detection and correction system. The system diagram in FIG. 1 includes the basic functions needed to perform an error detection and correction. These are: reading in and storing data while generating first check bits; reading out the stored data and generating second check bits; using the syndrome bits to indicate errors and to signal error correction circuitry. The problems encountered in using the system disclosed in U.S. Pat. No. 4,523,314 or a similar binary system in the trinary mode of the invention are numerous. The basic problems are the storing of trinary data; the generation of a check trit; the generation of syndrome elements; the error decoder and error detection procedure; and the error correction function. The known techniques for performing these functions in binary are not applicable to a trinary system without making unique and basic changes to the known prior art. Known binary storage devices such as latches do not exist for trinary.
Binary check bit generators cannot be used as is or altered to perform the generation of trinary check trits. The binary syndrome generators are AND logic groups and do not function to generate three-level syndrome elements. Error detection and correction techniques in binary are based on the principle of errors have changed data from 0 to 1 or 1 to 0. U.S. Pat. No. 4,523,314 uses adders and carry detectors since binary loss or gain will be detected by loss or gain of carry. Trinary error correction techniques have to determine the level of data error, i.e. 0, or 1, or 2. None of the binary logic or techniques including the use of adders and carry detectors are therefore applicable.
U.S. Pat. Nos. 3,755,779; 3,896,416 and 4,631,725 are typical binary error correction systems which generate check bits and syndrome elements to perform error correction. Comparison of syndrome generation techniques show the use of modulo-two and summations to generate the syndrome bits. The binary one-zero summations are relatively simple from a logic standpoint, however, this approach could not be applied to trinary.
Not only do problems exist in using the binary techniques in generating syndrome elements in trinary, but also in using the syndrome elements to first detect, and then correct errors. Detection of the error in binary requires only the identification of the error bit location and not the type of error, i.e., whether a error bit location has increased or decreased. In binary, increase of a "zero" sets the bit to "one" while decrease of a "zero" also sets the bit to "one". Increase of a "one", sets the bit to "zero". Therefore in error detection for binary only the fact that the bit has changed need be recognized. In trinary, increase or decrease of trit position will set the trit of 0, 1, or 2 at any of the three levels. To perform error detection which can be used to perform correction in trinary type of error, i.e., an increase in value or a decrease in value must be established since the error can place the data value at one of three levels: 0, 1, or 2.
To perform data correction in binary requires merely that the bit position in error be reversed, i.e., 0 to 1, or 1 to 0. Correction of a dropped bit (decrease in value) or a picked-up bit (increase in value) is performed by bit reversal. See U.S. Pat. No. 3,755,779, Col. 20, lines 21-28 and U.S. Pat. No. 4,631,725, Col. 7, lines 5-12.
In summary, to perform data correction in trinary requires that the error be identified as to whether the data position has increased or decreased since a different value will exist for each condition. Also, the correction must perform either an incrementing or a decrementing of the bit position to restore the data to the original condition. Therefore, application of the known binary techniques of detection of errors by any change which occurs to data from 0 to 1 or 1 to 0 as similar and correction of this error by merely reversing that data is not applicable to trinary.
There is therefore a need for performing error detection and correction on three-level logic data which is not within the capabilities of the prior art binary systems and which overcomes the problems in trying to apply the binary concepts to trinary or other multi-level logic.